백준 14888 연산자 끼워넣기

백준 14888 연산자 끼워넣기는 아주 쉬운 dfs문제이다. 숫자 1 2 3 4 5 6 이 주어지고 사용할 수 있는 연산자 + - * / 의 갯수가 주어지면 이 연산을 사용하여 앞에서부터 차례대로 연산한 결과의 최대값, 최솟값을 구하는 문제이다.

연산자 우선순위를 고려해야 하는 문제이면 꽤나 까다로운 문제이겠지만 순서대로 계산하므로 어렵지 않은 문제이다. 수의 개수 N이 최대 11이고 연산의 갯수가 최대 N-1이기 때문에 4^10 즉 2^20 1,048,576의 연산밖에 일어나지 않는다. 따라서 단순히 dfs를 통해 모든 경우를 해보아도 2초라는 시간은 충분하다.

아래의 코드는 단순히 +,-,*,/의 연산을 하며 계산결과를 누적하고 depth에 다달했을때 최대, 최소의 값을 갱신하는 코드이다.

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<set>
#define INF 987654321
using namespace std;

int n;
vector<int> arr;
int oper[4];

int dep;
int mx = -INF;
int mn = INF;

void dfs(int depth,int sum)
{
	if (depth == dep)
	{
		mx = max(mx, sum);
		mn = min(mn, sum);
	}

	for (int i = 0; i < 4; i++)
	{
		if (oper[i] > 0)
		{
			oper[i]--;
			dfs(depth + 1, sum + arr[depth + 1]);
			oper[i]++;
		}
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int numb;
		cin >> numb;
		arr.push_back(numb);
	}
	cin >> oper[0] >> oper[1] >> oper[2] >> oper[3];

	dep = oper[0] + oper[1] + oper[2] + oper[3];

	dfs(0, arr[0]);

	cout << mx << '\n' << mn<<'\n';
}